package leetcode;
/**
 * 416.分割等和子集
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等.
 *
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11]
 *
 * 输入：nums = [1,2,3,5]
 * 输出：false
 * 解释：数组不能分割成两个元素和相等的子集
 */
public class Num_416 {
    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1,5,11,5})); //true
        System.out.println(canPartition(new int[]{1,2,3,5})); //false
        System.out.println(canPartition(new int[]{2,2})); //true
    }
    //动态规划, 类似于砝码称重
    public static boolean canPartition(int[] nums) {
        //不可能成功的情况
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            sum += nums[i];
        }
        if(nums.length < 2 || sum % 2 != 0){
            return false;
        }

        int n = nums.length;
        //前i个元素是否可以拼凑出j值
        boolean[][] dp = new boolean[n+1][sum/2+sum];
        //初始化
        dp[0][0] = true;
        for(int i=1; i<=n; i++){
            //前i个一定可以凑出第i个整数
            dp[i][nums[i-1]] = true;
            for(int j=1; j<=sum/2; j++){
                //看前i-1个是否能凑出j
                if(dp[i-1][j]){
                    //一定可以凑出j
                    dp[i][j] = true;
                    //还可以凑出(j+第i个整数)
                    dp[i][j+nums[i-1]] = true;
                }
            }
        }
        //前n个整数能否凑出(和/2)
        return dp[n][sum/2];
    }

    /** 复习 **/
    public boolean canPartition2(int[] nums) {
        //想如何转为0-1背包问题？ 或接近于0-1背包的解题思路？
        //先求数组总和
        int sum = 0;
        for(int i : nums){
            sum += i;
        }
        //一定不能分割等和子集的情况
        if(sum % 2 != 0){
            return false;
        }
        //假设有一个背包的容量为(sum/2),不就是从数组中找出一些元素刚好填满这个背包吗？
        int bag = sum / 2;
        //dp[i][j] 表示前i个元素能否刚好填满容量为j的背包
        boolean[][] dp = new boolean[nums.length + 1][bag + 1];
        //先遍历元素
        for(int i = 1; i <= nums.length; i++){
            //再遍历背包容量
            for(int j = 1; j <= bag; j++){
                //先考虑是否选第i个元素
                if(dp[i-1][j]){
                    //如果前i-1个元素就能填满背包，则前i个也能
                    dp[i][j] = true;
                    continue;
                }
                //比较第i个元素和背包容量的大小
                if(nums[i - 1] > j){
                    //当第i个大于背包容量时
                    dp[i][j] = dp[i-1][j];
                }else if(nums[i - 1] == j){
                    //当第i个刚好等于背包容量时
                    dp[i][j] = true;
                }else{
                    //当第i个<背包容量时
                    dp[i][j] = dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[nums.length][bag];
    }
}
